package leetcode.set_map;

import java.util.HashMap;
import java.util.Map;
import java.util.Set;

/**
 * 242. 有效的字母异位词
 * <p>
 * 给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
 * <p>
 * 示例 1:
 * <p>
 * 输入: s = "anagram", t = "nagaram"
 * 输出: true
 * <p>
 * 示例 2:
 * <p>
 * 输入: s = "rat", t = "car"
 * 输出: false
 * <p>
 * 说明:
 * 你可以假设字符串只包含小写字母。
 * <p>
 * 进阶:
 * 如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？
 * <p>
 * 分析得出：也就是说判断t中的元素是否是s中的元素。不用惯顺序，考虑到右重复元素频率问题，这里需要使用hashMap进行存放
 */
public class Solution242 {
    public static boolean isAnagram(String s, String t) {

        //字符串的编码，是否为null。以及为null时候的处理情况。这里题目没有要求
        Map<Character, Integer> freq = new HashMap<>(52);//使用map可以在O(1)级别解决查询
        for (int i = 0; i < s.length(); i++) {
            char key = s.charAt(i);
            Integer value = freq.get(key);
            if (value != null) {
                freq.put(key, freq.get(key) + 1);
            } else {
                freq.put(key, 1);
            }
        }

        //遍历t，判断t是否在s中出现过，也就是包含在freq中
        for (int i = 0; i < t.length(); i++) {
            char c = t.charAt(i);
            if (freq.containsKey(c) && freq.get(c) > 0) {
                freq.put(c, freq.get(c) - 1);
            } else {
                return false;
            }
        }
        //看第一个数组是否已经没有元素,为了防止第二个字符串是第一个的子串等特殊情况.
        for (Character key : freq.keySet()) {
            Integer value = freq.get(key);
            if (value != 0) {
                return false;
            }
        }

        return true;
    }

    public static void main(String[] args) {
        String s = "rat", t = "car";
        System.out.println(isAnagram(s, t));
    }
}
